1. Field of the Invention
The present invention relates to mechanisms for protecting software against unauthorized use and, in particular, against unauthorized copying and license violation.
2. Description of the Related Art
The Business Software Alliance estimates the 1995 financial losses attributed to software piracy as US$ 8.1 Billion for business application software and US$ 15.2 Billion for all software.
Solutions have been proposed in two areas:
improved Intellectual Property Rights (IPR) legislation, and enhanced electronic copy and license protection (ECP) mechanisms. PA0 Unauthorized users or customers should be prohibited from executing protected software. PA0 Customers should be prohibited from executing software without a valid license. PA0 The customer should not be prohibited from making backup copies of the software. PA0 The ECP mechanism should have minimal impact upon the user interface. The visible impact should be limited to the first initial login to the operating system and/or smart card. PA0 Only standard hardware and software assumptions should be made. For example, although hardware dongles provide copy protection services, many vendors do not wish to limit the sale of the software to the collection of customers who own or are willing to install a dongle. PA0 The ECP mechanism should not limit execution of the protected software to a limited collection of machines. When a customer legitimately purchases software, the customer should be able to execute the software on any machine regardless of ownership. The customer should optionally be able to authorize simultaneous execution of the software in multiple machines. PA0 The ECP mechanism should have no required network dependencies in order to execute an already purchased protected program. PA0 The vendor should be permitted to distribute an identical version of the protected software to all customers. This requirement permits the protected software to be distributed through normal channels such as, for example, CD-ROMs, floppy disks, or network bulletin boards. PA0 It should be excessively difficult and/or computationally infeasible for a potential software pirate to circumvent the ECP mechanism without modifying the protected program. This requirement also serves as an virus-protection measure because a digital signature supplied by the vendor would not validate if a pirate distributes a modified version of the original program. PA0 The ECP mechanism should not disclose the private keying material to the vendor, to any program produced by the vendor, or to any potential Trojan horse program. Though the primary functionality is to protect the software vendor, one must not do so at the expense of the customer. PA0 The ECP mechanism should be available in a software-only version as well as in a hardware-assisted version, using a smart card, for example, to assure widespread market acceptance. PA0 a. Using the prime factorization, p and q, suitable for use in the computation of an RSA-like key pair, compute n=p.multidot.q and .PHI.=(p-1)(q-1) PA0 b. A defines a public exponent .upsilon..gtoreq.3 with gcd(.upsilon.,.PHI.)=1 where .PHI. and gcd is the Greatest Common Divisor. PA0 c. A computes a private exponent s=.upsilon..sup.-1 (mod .PHI.) PA0 d. System parameters (.upsilon.,n) are made available as the public keying material. PA0 a. A selects and publishes a well known identity I and the redundant identity J=.function.(I) satisfying 1&lt;J&lt;n using a known redundancy function .function.. An example of the redundancy function .function. is the redundancy mapping of the preprocessing stage of ISO/IEC 9796, see the Rivest publication. PA0 b. A retains as the private keying material s.sub.A =J.sup.-s (mod n). PA0 a. A selects a random secret integer r (the commitment), 1.ltoreq.r.ltoreq.n-1, and computes (the witness) x=r.sup..upsilon. (mod n) PA0 b. A sends to B the pair of integers (I,x) PA0 c. B selects and sends to A, a random integer e (the challenge), 1.ltoreq.e.ltoreq..upsilon. PA0 d. A computes and sends to B (the response) y=r.multidot.s.sub.A.sup.e (mod n) PA0 B receives y, constructs J from I using .function., computes z=J.sup.e .multidot.y.sup..upsilon. (mod n) and accepts A's proof of identity if both z=x and z#0. PA0 Z.sub.n is the set of integers modulo n PA0 Z.sub.n *={X.epsilon.Z.sub.n .vertline.gcd(x,n)=1} PA0 A.fwdarw.B denotes that A sends a message to B; and B.fwdarw.A denotes that B sends a message to A. PA0 r denotes a random number used as a nonce PA0 h(r) is a message digest of the nonce PA0 P.sub.A (r,B) is encryption of the nonce and B's identity using A's public keying material PA0 a) zero-knowledge-proofs, where it is provable that B or any observer of the proof learns nothing from the proof, except the fact that A possesses the private keying material. PA0 b) witness-challenge-response-proofs, which comprise the following four elements in a sequence: PA0 a) the first challenge means has no access to the private keying material accessed by the first response means, PA0 b) the first challenge means validates an asymmetric proof of the first response means that the first response means has access to the private keying material without requiring that the first response means disclose the private keying material, PA0 c) the second challenge means validates a proof of the second response means that the second response means has access to the secret keying material, PA0 d) the first challenge means or the second challenge means prohibit using the protected item of software or prohibit using the software in an unlimited mode unless either or both of the validations is or are successful.
IPR legislation and enforcement are improving in many countries, but there are still significant difficulties in other parts of the world. As a result, some software vendors are currently reassessing ECP.
Some example requirements that an ECP mechanism may potentially satisfy the need for piracy prevention are listed below:
In the publication by Choudhury et al., entitled, "Copyright Protection for Electronic Publishing over Computer Networks", a mechanism is proposed in which a protected document can be viewed only via a specially configured viewer program, which allows a customer to view the document only if the customer supplies to the viewer the customer's private keying material. This deters the customer from distributing unauthorized copies of the viewer program, since that would require the customer to divulge his or her private keying material to others. However, because this mechanism requires that the viewer program obtain access to the private keying material, it breaks one of the requirements described above. Furthermore, this mechanism may not be used in conjunction with a smart card that is configured to avoid releasing private keying material.
An overview on asymmetric cryptography, for example on the RSA (Rivest-Shamir-Adleman) scheme, symmetric cryptography, and probabilistic encryption, for example the Blum-Goldwasser probabilistic public-key encryption scheme can be found in "Handbook of Applied Cryptography" by Menezes, et al.
An overview of digital signature schemes (e.g. Rivest-Shamir-Adleman (RSA) scheme, etc.,) and a formal mathematical definition of digital signatures can be found in the Menezes book.
An example of a message digest function (otherwise known as a one-way hash function) is MD5 as described in the publication by Rivest, "The MD5 Message-Digest Algorithm". It is computationally infeasible or very difficult to compute the inverse of a message digest.
The Chi-Square Test, the Kolmogorov-Smirnov Test, and the Serial Correlation Test are described in "The Art of Computer Programming" by Knuth.
In the publication by Fenstermacher et al., cryptographic randomness from air turbulence in disk drives is described.
An overview over different probabilistic proof schemes, for example zero knowledge proof schemes (e.g. Feige-Fiat-Shamir scheme, Guillou-Quisquater scheme, Blum-Feldmann-Micali scheme, Brassard scheme, Crepau scheme, etc.) or witness hiding proof schemes (e.g. Feige-Shamir scheme, etc.) can be found in the Menezes book.